Fast Transforms for Gaussian Random Fields

The spectral properties of functions and operators provide key insights into their structure, and form the basis for state-of-the-art computational methods for simulation, learning, and inference. By providing a fast transform between space and frequency, the Fast Fourier Transform (FFT) revolutionized applications across computational mathematics. However, there remain many settings in which spectral methods cannot be efficiently applied because the geometric or analytic structure of the problem is not directly amenable to the FFT. Motivated by parameter estimation and sampling of Gaussian random fields (GRFs) in spatial statistics and uncertainty quantification, we introduce numerical methods in two such settings. 

First, we develop a Nonuniform Fast Hankel Transform for computing Fourier transforms of radially symmetric functions in higher dimensions. Next, we present a Fast Manifold Harmonic Transform for performing Fourier analysis on arbitrary smooth manifolds by leveraging a multilevel low-rank approximation known as a butterfly factorization. In each case, we demonstrate how these fast transforms can accelerate computations with GRFs, as well as applications in imaging, graphics, and numerical partial differential equations.